package com.zbxx.leetcode.tree;

import com.zbxx.leetcode.struct.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 655 输出二叉树
 *
 * @author wanrj
 * @date 2023/6/7
 */
public class printTree {

    public List<List<String>> printTree(TreeNode root) {
        int depth = calculateDepth(root);
        int column = (int) (Math.pow(2, depth) - 1);
        List<List<String>> ans = new ArrayList<>(depth);
        for (int i = 0; i < depth; i++) {
            List<String> strs = new ArrayList<>();
            for (int i1 = 0; i1 < column; i1++) {
                strs.add("");
            }
            ans.add(strs);
        }
        ans.get(0).set(column / 2, String.valueOf(root.val));
        dfs(root, column / 2, ans, 1, depth);
        return ans;
    }

    private void dfs(TreeNode root, int parentIndex, List<List<String>> ans, int listindex, int depth) {
        int column = depth > 2 ? (int) Math.pow(2, depth - 2) - 1 : 0;
        if (root.left != null) {
            ans.get(listindex).set(parentIndex - column - 1, String.valueOf(root.left.val));
            dfs(root.left, parentIndex - column - 1, ans, listindex + 1, depth - 1);
        }
        if (root.right != null) {
            ans.get(listindex).set(parentIndex + column + 1, String.valueOf(root.right.val));
            dfs(root.right, parentIndex + column + 1, ans, listindex + 1, depth - 1);
        }
    }


    public int calculateDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(calculateDepth(root.left), calculateDepth(root.right));
    }


}
